package com.cat.dataStructure02;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

/**
 *   @description https://leetcode.cn/problems/find-k-pairs-with-smallest-sums/
 *   @author 曲大人的喵
 *   @create 2025/10/28 20:12
 *   @since JDK17
 */

public class Solution75 {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> ans = new ArrayList<>(k);
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        heap.add(new int[] {nums1[0] + nums2[0], 0, 0});
        int n = nums1.length, m = nums2.length;
        for (int i = 0; i < k; i++) {
            var temp = heap.poll();
            int x = temp[1], y = temp[2];
            ans.add(List.of(nums1[x], nums2[y]));
            if (y == 0 && x + 1 < n) {
                heap.add(new int[] {nums1[x + 1] + nums2[y], x + 1, y});
            }
            if (y + 1 < m) {
                heap.add(new int[] {nums1[x] + nums2[y + 1], x, y + 1});
            }
        }

        return ans;
    }
}
